package a.codetop;


import org.junit.Test;

import java.util.Collections;
import java.util.PriorityQueue;

public class _3堆排序_第k大的数 {

    public int findKthLargest(int[] nums, int k) {
        Dui dui = new Dui(nums.length);
        for (int num : nums) {
            dui.add(num);
        }
        int res=-1;
        for (int i = 0; i <= nums.length-k; i++) {
            res=dui.poll();
        }
        return res;
    }
    class Dui {
        int cs=0;
        int[] h;
        Dui(int capa){
            h=new int[capa+1];
        }

        void down(int u){
            int t = u;
            if(u * 2 <= cs && h[t] > h[u * 2]) t = u * 2;
            if(u * 2 + 1 <= cs && h[t] > h[u * 2 + 1]) t = u * 2 + 1;
            if(u == t)return;
                swap(u, t);
                down(t);
        }
        public  void up(int u){
            if(u / 2 > 0 && h[u] < h[u / 2]){
                swap(u, u / 2);
                up(u/2);
            }
        }

        //插新
        void add(int val){
            h[++cs]=val;up(cs);
        }
        //删最小
        int poll(){
            //顶部是1不是0
            int out = h[1];
            h[1]=h[cs--];down(1);
            return out;
        }

        void swap(int i,int j){
            int t=h[i];
            h[i]=h[j];
            h[j]=t;
        }
    }
}
//笔试时
//    @Test
//    public void test() {
//        int[] p={3,2,1,5,6,4};
//        System.out.println(findKthLargest(p,2));
//    }
//
//    public int findKthLargest (int[] nums, int k) {
//        PriorityQueue<Integer> q = new PriorityQueue<>(Collections.reverseOrder());
//        int res = nums[0];
//        for (int num : nums) {
//            q.add(num);
//        }
//
//        for (int i = 0; i < k; i++) {
//            res = q.poll();
//        }
//        return res;
//    }
